package Solutions

import "container/heap"

type pair_getKth []int
type pq_getKth struct {
	data []pair_getKth
}

func (p pq_getKth) Len() int {
	return len(p.data)
}
func (p *pq_getKth) Push(a interface{}) {
	p.data = append(p.data, a.([]int))
}
func (p *pq_getKth) Pop() interface{} {
	item := p.data[len(p.data)-1]
	p.data = p.data[:len(p.data)-1]
	return item
}
func (p *pq_getKth) Swap(i, j int) {
	p.data[i], p.data[j] = p.data[j], p.data[i]
}
func (p *pq_getKth) Less(i, j int) bool {
	if p.data[i][1] < p.data[j][1] {
		return true
	} else if p.data[i][1] == p.data[j][1] {
		return p.data[i][0] < p.data[j][0]

	} else {
		return false
	}
}

func getKth(lo int, hi int, k int) int {
	var p = pq_getKth{}
	p.data = make([]pair_getKth, 0, hi-lo+1)
	cache := make([]int, hi*3+1)
	heap.Init(&p)
	heap.Init(&p)
	if lo == 1 {
		heap.Push(&p, []int{1, 0})
		lo++
	}
	var getTh func(i int) int
	getTh = func(i int) int {
		if cache[i] != 0 {
			return cache[i]
		}
		var ans = 0
		if i&1 == 1 {
			ans = getTh(3*i + 1)
		} else {
			ans = getTh(i / 2)
		}
		cache[i] = ans
		return ans
	}
	cache[2] = 1
	for lo <= hi {
		heap.Push(&p, []int{lo, getTh(lo)})
	}
	ans := 0
	for i := 0; i < k; i++ {
		ans = heap.Pop(&p).([]int)[0]
		lo++
	}
	return ans

}
